package leetcode.D300.T240;

class Solution {
    private boolean isFind = false;
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        return search(matrix, target, 0, n-1, 0,m-1);
    }
    private boolean search(int[][] matrix, int target, int left, int right, int up, int down) {
        if(left > right || up > down) return false;
        if(target < matrix[up][left] || target > matrix[down][right]) return false;
        int midColumn = binearySearch(matrix, target, left, right+1, up, true);
        int midRow = binearySearch(matrix, target, up, down+1, left, false);
        if(isFind) return true;
        return search(matrix, target, left+1, midColumn-1, up+1, midRow-1) ||
                search(matrix, target, midColumn, right, up+1, midRow-1) ||
                search(matrix, target, left+1, midColumn-1, midRow, down);
    }
    private int binearySearch(int[][] matrix, int target, int left, int right, int loc, boolean isRow) {
        if(isRow) {
            while(left < right) {
                int mid = (left + right) / 2;
                if(matrix[loc][mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if(target == matrix[loc][left-1]) {
                isFind = true;
            }

        } else {
            while(left < right) {
                int mid = (left + right) / 2;
                if(matrix[mid][loc] <= target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if(target == matrix[left-1][loc]) {
                isFind = true;
            }
        }
        return left;
    }
}
